% Implementation is split into two files

Let us define some basic concepts that will be used later on in this document. 
Since we are working with references, a \textit{reader} monad transformer\cite{Reader} 
is used to keep track of these in a read-only fashion. Monad transformers are 
used to add several layers of monads to combine their functionality as a new monad. 
Here we encapsulated the ST monad within the reader transformer to store and manipulate 
a state where the memory is represented by mutable arrays and internal registers by 
value references. ST stands for State Thread, and works as follows: the ST monad 
holds an internal state and each operation performed in the monad, updates this 
internal state. So far, the ST monad works very much like the IO monad but without I/O 
operations. The main difference is that actions performed in the ST monad are 
indexed by a type variable \textit{s}, which is quantified so that no two ST threads 
may interact with each other, achieving a clean separation of actions in a controlled 
manner. The only way to get actual values out from the ST monad is to invoke runST 
which has the following type: \cite{ST}
\begin{code} 
    runST :: (forall s. ST s a) -> a 
\end{code}

\input{./cpuimpl.tex}
\input{./ppuimpl.tex}

\section{Synchronization \& Communication}
Since we modelled the CPU and the PPU as two separate components as they also 
are by design in hardware, we needed a simple and efficient way to synchronize 
information between them. Our solution was to use a kind of message-passing where 
we utilized infinite lazy lists that pass around \textit{Actions} between the two components. 

\begin{code}
data Action
    = Read Address
    | Write Address Operand
    | DMA [Operand]
    | NMIRQ
    | NOP
\end{code}

Actions are produced for every step in the execution of the CPU and PPU, default action 
being \textit{no operation} (NOP) which means that nothing of interest has 
happened hence no need for synchronization. When a read or write is made on the 
shared registers (0x2000-0x2007), a \textit{Read} or \textit{Write} action is 
sent respectively by both CPU and the PPU.

When the CPU writes to 0x4014 a DMA action is encoded and sent together with 
256 bytes to be inserted into OAM by the PPU. Last \textit{Action} is the 
NMIRQ which is sent when the PPU is done generating a frame to signal v-blank.
\begin{code}
writeMemory :: Address -> Operand -> CPU s ()
writeMemory addr op
    ...
    -- PPU shared registers (with mirroring)
    | addr <  0x4000 = do
      let addr' = (0x2000 + addr `mod` 8)
      mem <- asks ppuMem
      lift (writeArray mem addr' op)
      setAction (Write addr' op)
    -- DMA
    | addr == 0x4014 = do
      let addr' = op * 255 
      ops <- forM [addr'..addr'+255] readMemory
      setAction (DMA ops)
    ...
\end{code}
As explained above, the code excerpt shows the encoding of actions performed
when writing to memory in the CPU. The PPU works in a similar fashion. \\

For each step the components run, they synchronize by decoding the actions sent
from the other component. For the CPU, this looks as follows (the CPU is only
interested in writes and NMI).
\begin{code}
cpuDecodeActions :: [Action] -> CPU s ()
cpuDecodeActions = mapM_ handle
    where
        handle a = case a of
            Write addr op -> do
                mem <- asks ppuMem 
                lift (writeArray mem addr op)
            NMIIRQ        -> setVar irq (Just NMI)
            _             -> return ()
\end{code}

\section{Enterprise Pulling}
The enterprise pulling (EP) is a technique we use for communicating between the 
CPU and the PPU. It is responsible for delivering messages between the two 
components of the program. EP relies on the fact that laziness in Haskell makes 
it possible to use infinite lists. Two separate infinite lazy lists are used; 
the list of CPU actions which is fed to the ppu function, and the list of PPU 
actions which is fed to the cpu function (figure below). Each step in the cpu 
and ppu functions respectively consumes one element in the input list, and 
produces one element in the output list. Thus, only one element in each list 
will be computed at each step in the program.

The enterprise pulling is initiated as follows:
\begin{code}
enterprisePulling :: [Maybe Input] -> [Pixel]
enterprisePulling keys = pixels
    where (actions, pixels) = ppu (cpu keys actions)
\end{code}

Relying on Haskell being lazy, one can use the "actions" in the cpu function even 
though "actions" has not yet been computed. Since the Enterprise pulling works 
by taking advantage of this inherent functionality, nothing is computed until it 
actually is needed. This makes it easy to control the emulation speed, since only 
the output that is visible to the user are the pixels returned by the PPU. By adding 
latency in the PPU, latency will automatically be achieved in the CPU as well.
\begin{figure}[h!]
    \begin{center}
        \includegraphics[width=200px]{images/enterprise.png}
        \caption{Enterprise Pulling}
    \end{center}
\end{figure}

\section{I/O}
The only output in the program are the pixels generated by the PPU, which are 
passed to the graphics library (SDL). The input to the program is a lazy list of 
key events. This list is checked in each step of the cpu loop, and if the first 
element in the list is \textit{Nothing}, then nothing is performed, otherwise the value 
corresponding to the pressed key is written to the appropriate memory location 
(0x4016 for P1, 0x4017 for P2). The unfortunate thing about the input is the need 
for \textit{unsafeInterleaveIO} since the IO monad is strict and we want the list 
to be lazy. The use of unsafeInterleaveIO makes the function terminate at once,
but nothing is computed. When the value of the unsafe call is needed, it is going
to start computing. \cite{unsafe}

\subsection{SDL \& Graphics}
We have chosen to use SDL as the front-end library for this project. 
This was a natural choice for us, since SDL supports both graphics, input and sound. 
Even though sound is not considered at this point, it is convenient not to have 
to change the library if the time comes. Since SDL is only responsible for drawing 
pixels to the screen and for polling keyboard events, the code required for this 
to work was very small. \cite{SDL}
\begin{code}
draw :: [(Pixel,Int,Int)] -> IO ()
draw pxs = do
    surface <- getVideoSurface
    forM_ pxs $ \(p,x,y) -> 
        fillRect surface (Just $ Rect x y 1 1) p
    SDL.flip surface
\end{code}

\subsection{Loading \& ROM layout}
Since most images be it hardware dumps from real game cartridges or homebrew 
games use some kind of a header to inform the emulator of various things such as 
the region format etc, the data had to be parsed correctly so we had to implement 
a basic loader for these images. Our choice was the \textit{iNes} header format since it 
is the one mostly used, a de facto standard in the NES community.

Size of the header is only 16 bytes and it holds important data needed by the 
emulators to load the games properly for example the number of program or code banks 
and character banks to load in to the emulator memory and the region format mentioned 
above. Character rom is loaded into the PPU memory as pattern data and the program 
rom is loaded into the main memory starting at location \textit{0xC000}. \\

The header for the iNES format looks as follows: \cite{ines}
\begin{itemize}
    \item Bytes 0-3: "NES".
    \item Byte 4: 0x1A.
    \item Byte 5: Number of 16K PRG ROM Banks.
    \item Byte 6: Number of 8K CHR ROM Banks.
    \item Byte 7: Control Byte (lsb)
        \begin{itemize}
            \item Bit 0: Mirroring
                \begin{itemize}
                    \item 0 = Horizontal Mirroring
                    \item 1 = Vertical Mirroring
                \end{itemize}
            \item Bit 1: Backed battery present (yes/no)
            \item Bit 2: Trainer data present (yes/no)
            \item Bit 3: Four screen mirroring (yes/no)
            \item Bits 4-7: Mapper id, four lower bits.
        \end{itemize}
    \item Byte 8: Control Byte (msb)
        \begin{itemize}
            \item Bit 0: VS Unisystem Arcade (yes/no)
            \item Bit 1: Playchoice-10 Arcade (yes/no)
            \item Bits 2-3: Not used
            \item Bits 4-7: Mapper id: four higher bits.
        \end{itemize}
    \item Bytes 9-15: Reserved, must be zeroes
\end{itemize}
